It is useful to search for similar pairs (or groups) of objects from a population of objects. For example, finding similar documents can be useful in document management, such as for removing duplicate documents in a database. The objects to be analyzed can be represented as vectors. Finding similar pairs of objects can involve computing similarity scores between pairs of vectors, and keeping track of which vectors (or which parts of the vectors) have already been compared. The similarity scores can be compared with a threshold, and pairs of vectors whose similarity scores above the threshold are provided as the search result. For example, given a dataset V of vectors, a similarity function sim(·, ·), and a threshold value t, one way to identify similar pairs of vectors is to compute sim(x, y) for all pairs of vectors x and y in the dataset V and identify the pairs of vectors x and y for which sim(x, y)≧t.